package com.sicheng.lc.周赛.分类.dp;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/8 20:03
 */
public class 将N变成1的最小操做次数 {
    /**
     * 输入正整数 n
     * 按规则转化数字最终变成1
     * x % 2 == 0: x = x / 2
     * x % 2 == 1: x = x*2+2或者x=x*2-2
     */
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // dp[i] 表示i变成1需要的最小代价
        int[] dp = new int[n + 1];
        for (int i = 1; (1 << i) <= n; i++) {
            dp[1 << i] = i;
        }

        for (int i = 3; i <= n; i++) {
            // dp[i] 已经预处理过或者被奇数处理过
            if (dp[i] > 0)
                continue;
            if ((i & 1) == 0)
                // i 为偶数不断除以2 得到一个奇数
                // i== (1<<cnt) * m ===> dp[m]以前肯定算过了
                //  好比 6 = 2 * 3===> 1 + dp[3]
                dp[i] = cnt(i, dp);
            else {
                int x = (i << 1) - 2;
                int y = (i << 1) + 2;
                // 如果很有幸x，y其中一个是2的次幂那么i直接变成2的次幂
                if (1 << dp[x] == x) {
                    dp[i] = 1 + dp[x];
                } else if (1 << dp[y] == y)
                    dp[i] = 1 + dp[y];
                else {
                    // 很不幸 x，y只是普通的偶数
                    dp[x] = cnt(x, dp);
                    dp[y] = cnt(y, dp);
                    // i 花费1个代价变成x,y
                    dp[i] = Math.min(dp[x], dp[y]) + 1;
                }
            }
        }

        System.out.println(dp[n]);

    }

    private static int cnt(int i, int[] dp) {
        int res = 0;
        while ((i & 1) == 0) {
            i >>= 1;
            res++;
        }
        return res + dp[i];
    }

}
